package com.shuang.greed17;

public class MinCameraCover {
    //思路：为了装最少的摄像头 要在叶子节点的父节点安装摄像头 这样监视了三层
    //所以后序遍历二叉树 从后向前找 叶子节点父节点装完后 父节点的上一层也被监视了 所以从父节点再往上跳两个节点 在第三个节点位置再装一个摄像头即可
    //递归二叉树时 用三个状态 表示节点即可
    //0：该节点无覆盖
    // 1：本节点有摄像头
    // 2：本节点有覆盖

    //定义全局变量用来记录摄像头数量
    int res = 0;

    public int minCameraCover(TreeNode root) {
        //情况四：4.如果最后递归出来的状态最后是2 说明根节点左右两个孩子都有覆盖 那么还要在根节点还要加一个摄像头才能监视到根节点
        if (minCamera(root) == 0){
            res++;
        }

        return res;
    }

    //递归处理二叉树
    private int minCamera(TreeNode root){

        //终止条件 遇到空要返回有覆盖的状态（只能是有覆盖 避免在叶子节点上放摄像头）
        if (root == null){
            return 2;
        }

        //后序遍历（左右中）
        int left = minCamera(root.left);
        int right = minCamera(root.right);

        //中
        //一共四种情况
        //其中三种情况:

        //1.左右孩子都有覆盖2 那么父节点应该为无覆盖状态0
        if (left== 2 && right == 2){
            return 0;
        }

        //2.左右孩子只要有一个是无覆盖了0  父节点就应该为有摄像头1
        if (left == 0 || right == 0){
            //要加摄像头了
            res++;
            return 1;
        }

        //3.左右孩子只要有一个有摄像头1 父节点就应该为有覆盖2
        if (left == 1 || right == 1){
            return 2;
        }

        //防止编译报错 走不到这里
        return -1;
    }
}
